package arithmetic.leecode_arthmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 删除链表的倒数第N个节点
 * 剑指offer算法第十九题
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution19 {

    public static void main(String[] args) {
        Solution19 solution19 = new Solution19();
        ListNode head = new ListNode(1,null);
//        ListNode one = new ListNode(2);
//        head.next = one;
//        ListNode two = new ListNode(3);
//        one.next = two;
//        ListNode three = new ListNode(4);
//        two.next = three;
//        ListNode four = new ListNode(-1);
//        three.next = four;
//
//        ListNode five = new ListNode(-1,null);
//        four.next = five;

        ListNode now = solution19.removeNthFromEnd(head, 1);
        System.out.println(now);

    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slowNode = start;
        ListNode fastNode = start;
        fastNode.next = head;

        for(int i = 1;i<= n+1;i++){
            fastNode = fastNode.next;
        }

        while (fastNode != null){
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        slowNode.next = slowNode.next.next;
        return start.next;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
